Query optimization involves the translation of a database query into an efficient program or query plan to be executed over the data stored in the database. The database query is typically stated in a query language, such as SQL (Structured Query Language), CQL (Contextual Query Language), and MDX (Multidimensional Expressions), among others, and converted into one or more possible query plans. A query plan specifies a set of steps that are used to modify or access the data for executing the query. Details such as how to access a given data relation, in which order to join data relations, sort orders, and so on, may form part of a query plan.
For a given query, a large number of query plans may be generated by varying different constituents of the query plan, such as access paths, join methods, join predicates, and sort orders. The cost of a query plan can be modeled in terms of various parameters, including, for example, the number of disk accesses and the response time required to fetch data. A query optimizer may evaluate the costs of all possible query plans for a given query and determines the optimal, i.e., most efficient plan for executing the query.
A single query may require a large number of optimization jobs—typically in the hundreds of thousands for queries of medium complexity. Each job corresponds to the optimization of a sub-problem of the original query optimization problem. A scheduler in the query optimizer is responsible for scheduling the execution of the multiple jobs corresponding to a given query.
Query optimization jobs may have strong interdependencies, i.e., certain jobs are only applicable after other jobs have been executed. Since the dependencies are the result of ongoing optimization, they are not static and cannot be determined upfront. Dependencies between jobs result from the fact that a given parent job may entail additional dependent jobs. For the parent job to finish, all of its dependent jobs have to be completed. The dependent jobs can themselves become parent jobs and entail further dependents in turn. A parent-dependent relationship is therefore a 1:N relationship—there is no limit on how many dependent jobs a given parent can produce.
The number and type of the dependent jobs for a given parent is generally determined at run time and it is a function of the particular query being executed. The decision to spawn dependent jobs is made by the parent job based on external data structures. Because jobs are self-contained, when re-executed after their dependents are complete they can infer that all their dependent jobs have completed.
Query optimization has been one of the most active fields in database research, with a plethora of optimization techniques developed over the course of the past three decades. One of the most popular query optimizers is provided by the Cascades framework described in G. Graefe, “The Cascades Framework for Query Optimization,” IEEE Data Engineering Bulletin, 18(3), pp. 19-29, September 1995.
The Cascades query optimization framework encodes dependencies using a stack-based scheduler. All pending jobs are kept in a stack and the top-most job is the next to be executed if and only if no other job is currently being executed, i.e., this assertion is only valid between execution of jobs. Consider for example, the stack illustrated in FIG. 1 showing five optimization jobs, labeled from j1 to j5. After a number of executions, the stack looks as depicted in stack 105 with j1-j3 waiting to be executed and no job running. Since j3 is at the top of the stack, it is the next job to be executed. The stack-based scheduler then removes j3 from stack 105 and assigns it to a thread for execution. The stack is then changed into stack 110.
Throughout stacks 110-120, job j3 is running. Since j3 entails additional jobs, it puts itself back onto the stack 115 and adds dependent jobs j4 and j5 to stack 120. Job j3 then returns control to the scheduler, which starts executing j5. Once j5 and j4 are complete, j3 is again the top-most job in stack 125 and can now proceed without spawning additional dependents. Once j3 is complete, control is returned to the scheduler for starting job j2 in stack 130 and so on. The optimization is complete when the stack becomes empty and all jobs have executed.
As illustrated in FIG. 1, the stack-based scheduler used in the Cascades framework cannot be used for scheduling jobs to more than one thread at a time as the stack reflects dependencies correctly only between the executions of jobs. That is, in the example provided in FIG. 1, the stack is not in a well-formed state in stacks 110 and 115. Executing job j2 in stack 110 would break the query optimization process since in stack 115 job j3 puts itself back on the stack for the purpose of spawning its dependent jobs j4 and j5.
The problem with single thread execution is that this query optimization framework is not suitable for the more recently developed multi-core architectures, which combine multiple computing cores (e.g., CPUs or Central Processing Units) into a single processor or integrated circuit. Because query optimization is known to be computationally very intensive, higher CPU performance immediately translates into better and faster optimization results. The performance impacts can easily reach an order of magnitude in running time or more.
Continuous increases in CPU performance dictated by Moore's Law have previously translated into query optimization becoming better automatically as more optimization jobs can be executed within the same amount of time. Due to the current physical restrictions on miniaturization and clock speed in CPUs, future increases in CPU performance come from these multi-core architectures, e.g., dual-core, quad-core, etc., instead of faster single-core CPUs.
Accordingly, it would be desirable to provide query processing techniques that take advantage of the performance increases provided by multi-core architectures. In particular, it would be highly desirable to provide techniques to parallel process a query across multiple parallel threads in a multi-core architecture.